2020年 GW コンパイラづくりまとめ

の続きをやっていく

自分への備忘録もかねて書いておく

Day1 2020/5/2

とりあえず、去年の最後のコミットは

で、2019年6月2日

そこから、構造体の実装をしようとどん詰まりして、時が過ぎ去ってしまった模様

ということで、まずは去年の復習からスタート

すっかり忘れている

Day2 2020/5/3

ひたすら復習〜

自分のコードを読み直してもうっすらとしか思い出せない

やはり少しでもいいから続けないと取り戻すのに時間がかかってしゃあないということを思い知る。

前に少し書いていたコードは捨てて、新たに構造体のサイズをとるところからスタートすることにする。

code: こんなやつが取れるようになった

"int main() { struct { char a; char b; struct { char a; int b; } c; } x; return sizeof(x); }"

＜閑話休題＞ ここで、実装していく方針

テキストは、途中までしかないので、この先は基本は、コミットをみながらそれを一つずつ写経っぽく実装していく

大枠は真似っこで実装しつつ、うまく動かないところをデバグしていく

何を実装しようとしているかはコミットメッセージを見るのと、一番大きいのは、テストコードを見ること

これにより、このコード修正で実現しなければいけないことを理解できる

Day3 2020/5/4

ここまで。

この辺は特につまることもなく、サクサク実装できた。

やはりしっかり復習をしたことがよかった模様

Day4 2020/5/5

どんどん新規の実装を追加していく

この辺りは、こんな簡単でいいんかねぇ・・まぁゆうて真似してるだけだしなって思ってた

typedef / void / ! operatorなどを実装していった

特に大きな問題はなかった・・

ここまでは・・・

Day5 2020/5/6

世間的にはGW最終日

気持ちよく終わろうということで、せっかくだから自作コンパイラでテストを書いて動かす部分を書いていこうとする

とりあえずざざっと 何もテストにならないが、0が0であることを検証するコードでもかくかーとprintfは外部リンクしてok/ngを吐き出すコードを書いてみる

次に、jmpコマンドの整合性が取れてなくて全然違うところに飛んでしまうバグに悩まされる・・

それも直して、よーーしと思ってコンパイルすると謎のSegmentation Fault

最小コードで検証していくと、printfに渡す時にABIの第一引数はrdiにセットしないといけないが、セットした後に、別の場所でrdiを利用していてSegmentation Faultを起こしていることを発見して、とりあえず、この場では、ABIで引数として使っているレジスタは、関数呼び出しの時にしか使用しないようにしてそれ以外の時は別のレジスタを使用することにして回避した

parseからちょっと変える必要があるというので、この日はここまで

Day6

延長戦

table: 書き方

A* Aを0回以上繰り返す

A? Aまたはε

A|B AかB

() グループ化

今実装してるのをEBNFで書いてみると

code: EBNF

toplevel = (type ident ( "(" param (, param)* ")" "{" compound-stmt )| vardef) ";"

param = type vardef

compound-stmt = (stmt) stmt* "}"

stmt = (type decl

| "if" "(" assign ")" stmt ("else" stmt)?

| "for" "(" type decl | expr-stmt) assign ";" assign ";" assign ")" stmt

| return assign ";"

| "{" (stmt)* "}"

| expr-stmt

decl = type ident ("=" assign)? ";"

expr-stmt = assign ";"

assign = logor ("=" logor)?

logor = logand("||" logand)*

logand = equality("&&" equality)*

equality = rel(("==" | "!=") rel)*

rel = add(("<"|">") add)*

add = mul(("+"|"-" mul)*

mul = unary("*"|"/" mul)*

unary = (("*"|"&") unary)

| ("sizeof" unary)

| postfix

primary = "(" ("{" compound-stmt ")" )? assign ")"

| num

| str

| ident ( "(" assign (, assign)* ")")

なんと、expectedをactualと同じ値にしてテストが全部パスするというバグが発覚した・・・

Day7へ続く

Day7

文 (statement)と式 (expression)の違いを正しく理解できてなかったことが起因して問題が起きていた

式 (expression): 値を一つ必ず残す

文 (statement): 値を必ず何も残さない

つまり、gen_exprをした後はスタックに必ず残っているが、gen_stmtした後は、値が残っていないようにしなければいけなく、これを前提にしてコードを書けば良い

では、compound statement (複文) はどうなるか？

そもそも compound statementは何か？

上(EBNF)にもあるように stmtが複数含むstatementである。

ので、値は必ず残っていない。

GNU拡張のstatement expressionは式

({ i = 3; })

みたいなやつ。これ自体は、値を一つ残す。

Day8

トークナイズをミスっていて、\"のようなエスケープされた部分でstringが終わっていると判定されたのがあったので修正した

Day9

externやら、三項演算子や, operatorを実装したらしい

このサイトでBNFが見れるということを発見して、parserを書くのが楽になってきた

Day10

bit演算子、 % operatorを追加

変数を配列定義に書くのが合法なのか？ということがよくわかっていない

その部分でうまく動かないコードがある

まだまだ動かない部分が多々ある。

Day11

今日も対応していない部分を実装していった

トークナイズのエスケープ周りが地味にだるい

Day12

後置・前置のincrement/decrementを実装

breakを実装

for

第一文に 定義文を書けるようにした。

Day13

string literalのサイズ計算が char literalと同じになっていたのをStringの長さから取得するように変更

semaでnodeの書き換えを行なっている

やり方がこれでいいのか？あるいは、codegenでやったほうがいいのか？

その辺りは謎である

hexadecimal/octalに対応

0xFFFF

0755

みたいなのも書ける

preprocessorのときだけ改行に対応するのがあまりよくわかっていない。

Day14

まずは単純な置き換えの実装

Day15

"abc" "def"

\ line continuation

switch-case

continue

sizeof(char)/sizeof(int)

などを実装して、

atcoder/edpc

k_stones.cがうまく動いたっぽい

Day16

code: array

aはCの文法上、配列型であるaの先頭のアドレスを返すことになっている。

今度は、mallocするケースを考える

code: malloc

int *a = malloc(2 * sizeof(int));

これは何を意味しているか？

くっつけると、aにはintのサイズが二つ分確保されたヒープ領域へのポインタが代入される

&aはローカル変数のアドレスが返る

Day17

本格的にちゃんとデバッグをしようと言うことでgdbを使えるようにするのを目標にする

まず、そもそも自分が吐き出したアセンブリだとうまくmainにbreakpointが貼れない問題があった

例えば

code: main.c

int main() {

return 1 + 3 - 2;

}

こう言うコードがあった時に

$ gcc -S main.c

でアセンブリをはくと

$ gcc -g main.s

で実行ファイルを作成してみると、gdbでmainにbreakpointを貼ることができる

一方、自作コンパイラで

$ ./9cc main.c

でアセンブリをはくと

同じように実行ファイルを作成しても、mainが見つからないと怒られる

この原因は、

自作コンパイラのはくアセンブリの冒頭の部分（なんて言うんだろう？）は

code: my.s

.intel_syntax noprefix

.data

.global main

こうなっていた

これを

code: my.s

.intel_syntax noprefix

.data

.text

.global main

ステップ実行する

si

スタックがどうなってるかをみる

スタックを一つだけ取り出してみる

$ (gdb) x/1gx $rsp

$ 0x7fffffffe5f8: 0x0000000000000001

スタックを上から四つ取り出す

$ (gdb) x/4gx $rsp

$ 0x7fffffffe5f8: 0x0000000000000001 0x0000555555554630

$ 0x7fffffffe608: 0x00007ffff7a05b97 0x0000000000000001

メモリの中身をみる

g - giant word (64-bit value)

x - hexadecimal

文字列

x/1ds $rax

placeholderを用意しておいてそこに繋ぐって言うやり方は、確かに型の読み方から考えるとそうだなぁと思いつつよくこんな方法が思いつくなぁと感心する・・

パス指定してincludeできるようになった。

が、#include <stdio.h>はまだ成功しない。

内部的には、.globlをつけるかどうかの違いっぽい？

Global変数の初期化をintだけ対応した。

値を1byteずつに区切って、吐き出すみたいだけどあまりよくわかっていない。

Day18

一個のファイルだけでもセルフコンパイルしたいと言うことで、やっていく

Day19

includeに難航中

int x[3] = {1, 2, 3};

のような文をパースできるようにしたい。

うまくいった

int x[3] = {};

char x[4] = "abc";

int x[] = {1, 2, 3, 4};

char x[] = "foo";

struct { int a; int b; int c; } x = {1, 2, 3};

struct {int a; int b;} x = {};

などを書けるようにした。

Day20

Global変数の初期化式を実装していく

code: scalar

char g3 = 3;

int g4 = 5;

int *g5 = &g4;

char *g6 = "abc";

文字列周りの処理が結構ややこしかったけど結局

これによってstring literalを要素に持つ配列でも同じように扱える感じになった。

sema.cのなかで閉じていたグローバル変数Mapを作る処理が、parseのなかでも行うようになったのでいずれ修正しないといけないかもしれないが、いったん大丈夫。

sema.cのND_STRの処理は消せる気がしてきた。（まだ消せていない)

Day21

enumの実装

ほとんど構造体と一緒だな。

プリプロセッサ再び・・・

問題はif/elseは通常のtokenとかぶっていて、ちょっと厄介だった。

TK_IF/TK_ELSEとして処理するのか

TK_IDENTのnameがendifなのか？みたいなのが微妙に違うので、厄介。

Day22

#elif

この辺は、昨日結構コードを読み込んだのでサクサク実装できた。うまく実装できてるかどうかはわからないけど笑

const/noreturnはいったんスキップすることに

stdio.hを読み込むと202010Lみたいな奴が読み込めないので

まずは、型を増やす方向性で

long

short

long long

long int

も対応。実際エイリアスとしてしか動いてない気がするけど意味あるんかな？

今の時点で4133行ほど

もうちょいな気がするけどなぁ・・・

Day23

unsignedの実装

まだキャストがないのでテストはちょっと微妙な感じなので、もうちょっと拡充したい

結局実装部分としては、codegenのなかで、8/16/32ビットのレジスタに乗っかってる値を符号拡張ありで展開するか、符号拡張なしで展開するかという部分に効いて来るだけっぽい

考えてみればそりゃそうかという感じ、今はlhsの型に合わせる形になってるが、キャストしたら両方のキャストを考慮する必要があるのか？あまりその辺りがよくわかっていない

selfhostに向けてstdio.hの読み込みと再度戦う

includeのファイル名に数字が入っているとうまく読み込めないバグを直した

preprocessor内の読み飛ばし処理のなかでelse句が来るとうまく読み飛ばせてなかったバグを修正した

alignofを実装

Day24

stdio.hとかはリアルに読み込まずに使っている関数はプロトタイプ宣言したり、defineしたりするようにした

struct/enumを変数なしで宣言だけできるように修正した

const/typedefなどが変数名についているときにスキップされるバグを修正した

main.cをセルフコンパイルすることに成功した

他のファイルは主にcastでしくってる模様

あとは、switch~caseのdefault がない部分

Day25

castを実装した。

結局、int/long/char/shortとかは上位ビットを落としたり、上位ビットを0で埋めて拡張したりするだけっぽい。

色々バグに気づくなど

今は、構造体の中に構造体を持つネストでエラーが起きてるっぽいのをなんとか潰そうと奮闘している段階

この週末は

型を増やしたり(long/short)、unsigned/signedに対応

ヘッダを読み込む際に色々バグっていたプリプロセッサ周りを修正

可変長引数に対応

キャストを実装

などしてました。

標準ライブラリのヘッダを読むのはかなり大変なので、とりあえず使用している関数やマクロだけ宣言しておいて、なんとか自分のヘッダファイルの読み込みに成功しました。

あとちょっとでいくつかのファイルがコンパイルできそう感が出てきましたが、ちょっと進んではセグフォト戦ってバグを治すというしんどいフェーズになってきた感があります笑

Day26

parse.c

のなかのstructureのメンバーアサイン定義の部分でうまくTypeを結合できていなかった。

main.cをコンパイルすると何故かクラッシュしたり、no input fileになったりする・・・

原因はとても見つけるのに苦労したが、

後置インクリメントや前置インクリメントで、変数のサイズを考慮しておらず、配列のindexに後置インクリメントを使った時に思わぬアドレスになってしまっていることが原因だった・・

code: main.c

for (int i = 1; i < argc; i++) {

continue;

}

あとは、no input fileになっていたのは !"hoge"が0として扱われていた。 ! operatorのバグであった

大変すぎた・・・

しかし、これでとうとう1ファイル（main.c）をセルフコンパイルすることに成功した。

Day27

code: eof

bool eof() {

return ctx->pos == ctx->input->len;

}

このようなコードなんだけど、

code: eof

bool eof() {

bool is_eof = (ctx->pos == ctx->input->len);

return is_eof;

}

こういう書き方をするとうまくいく

つまり呼び出し元で、結果をうまくハンドリングできてない気がする

if(!eof())

と書いた時に、上のコードだと、上位ビットがクリアされていないので、ゴミが残っていた時にfalseじゃなくなってしまうケースがあるのではないか。

Day28

引き続きpreprocessor.cのセルフコンパイル

関数の引数でboolがあるとロードできていなかった問題を修正

code: preprocess.c

static CondIncl *push_cond_incl(bool included) {

CondIncl *ci = calloc(1, sizeof(CondIncl));

ci->next = cond_incl;

ci->ctx = IN_THEN;

ci->included = included;

cond_incl = ci;

return ci;

}

こういうの

eaxのロードで上位ビットがバグる問題を修正

boolの変数にアサインした時に正しい領域にロードできていなかった問題を修正

code: preprocess.c

static Vector *read_const_expr() {

Vector *_tokens = copy_until_eol();

fprintf(stderr, "################## \n %s\n", t->input);

Vector *new_tokens = new_vector();

int i = 0;

while (i < _tokens->len) {

if (t->ty == TK_IDENT && !strcmp(t->name, "defined")) {

bool has_paren = false;

if (t->ty == '(') {

has_paren = true;

}

if (t->ty != TK_IDENT)

bad_token(t, "macro name must be an identifier");

char *name = t->name;

bool defined = find_macro(name);

if (has_paren) {

if (t->ty != ')') {

bad_token(t, "parenthes ')' is needed");

}

i++;

}

vec_push(new_tokens, new_num_token(defined ? 1: 0));

} else {

vec_push(new_tokens, t);

}

}

return new_tokens;

}

あと一関数っぽい

code: C2slackに報告した内容

ミスコンパイルのミスの箇所を特定し、一つずつ原因を潰していく作業を進行しています。

大体のバグがレジスタのサイズを正しく拡張できていなくて、上位ビットが残ったまま悪さしていたり、想定以上のメモリ領域を書き換えてしまって壊れているというものばかりで、逆によくテストケースでは、動いていたなと思ったりします笑

また、教えていただいた二分探索で1ファイル中のミスコンパイルの箇所を特定する作業をしていると、ミスコンパイルの箇所が複数あって、二分探索のどちらにもバグがあるということもあり場所の特定にも難航したりしますが、1関数ずつ直して行ってだんだんと安定性が増してきた気がします。

出来る限り見つけたバグはテストケースで落とすようにして、それを修正するようにしています。

もう少しで2ファイル目がセルフコンパイルできそうです。(2/ 7ファイル)

Day29 - Day34ぐらい・・？

parse.cをセルフコンパイル

code: placeholder.c

typedef struct PlaceHolder {

int val;

} PlaceHolder;

int main()

{

struct PlaceHolder *placeholder = calloc(1, sizeof(PlaceHolder));

struct PlaceHolder replaced;

replaced.val = 3;

placeholder->val = 5;

*placeholder = replaced;

return 0;

}

こんな感じで、placeholderが指すヒープにreplacedのstructをロードするコードが上手く動かなかったのをずっと戦っていた

structのサイズはレジスタに乗り切らない可能性があるので、1バイトずつ順にアドレスにコピーしていく形で実装した。

ようやくparse.cのコンパイルに成功した。

これで4ファイル目

Day35

util.cのコンパイル

諦めて可変長変数の読み込みはコードを書き直した・・・・(va_startとかその辺の）

それでもエラーが起き、原因がわからなかったが、

code: map_geti

int map_geti(Map *map, char *key, int undef) {

for (int i = map->keys->len -1; i >= 0; i--)

return undef;

}

このコードがミスコンパイルを引き起こしていることがわかった

ずっとintptr_tのところのキャスト周りかとあたりをつけて調べていたが、どうも違うらしいということでログを埋めながら検証していくと、何故かundefが-1で渡されているのに、返却されているのは-2になっていることが判明した

これは、上にもあった、後置前置インクリメントのバグと全く同じで、デクリメントに対応していないことで引き起こされていたつまり、サイズを考慮していないので、intなのに、0から-1された時にintの範囲を超えてデクリメントされた結果undefが保存されているメモリが破壊されていることに起因していた。

codegen.cをコンパイルする時に

stringの長さがcharで、長すぎるとばぐる問題があったので、修正

ついに第1世代コンパイルで全ファイルをコンパイルしたものをリンクしたものでテストが通った！！！

と思って、次に第二世代コンパイラのはくアセンブリのコードと第一世代コンパイラのdiffを取ったところいくつか差分があるので修正した

コードの書き方を変えて対応したので、そもそもどこがおかしいかは闇の中ではある・・

忘れないように直したコードはここに貼っておく

ともわれ、自分のコンパイラが吐いたバイナリでリンクした第二世代コンパイラでコンパイルしたものをリンクした第3世代コンパイラでテストをクリアした！

セルフホスト達成！！